Lower Bounds on Near Neighbor Search via Metric Expansion.

Ranking mechanisms in twitter%2Dlike forums.
We study the problem of designing a mechanism to rank items in forums by making use of the user reviews such as thumb and star ratings. We compare mechanisms where forum users rate individual posts and also mechanisms where the user is asked to perform a pairwise comparison and state which one is better. The main metric used to evaluate a mechanism is the ranking accuracy vs the cost of reviews, where the cost is measured as the average number of reviews used per post. We show that for many reasonable probability models, there is no thumb (or star) based ranking mechanism that can produce approximately accurate rankings with bounded number of reviews per item. On the other hand we provide a review mechanism based on pairwise comparisons which achieves approximate rankings with bounded cost. We have implemented a system, shoutvelocity [5], which is a twitter-like forum but items (i.e., tweets in Twitter) are rated by using comparisons. For each new item the user who posts the item is required to compare two previous entries. This ensures that over a sequence of n posts, we get at least n comparisons requiring one review per item on average. Our mechanism uses this sequence of comparisons to obtain a ranking estimate. It ensures that every item is reviewed at least once and winning entries are reviewed more often to obtain better estimates of top items.
A sketch%2Dbased distance oracle for web%2Dscale graphs.
We study the fundamental problem of computing distances between nodes in large graphs such as the web graph and social networks. Our objective is to be able to answer distance queries between pairs of nodes in real time. Since the standard shortest path algorithms are expensive, our approach moves the time-consuming shortest-path computation offline, and at query time only looks up precomputed values and performs simple and fast computations on these precomputed values. More specifically, during the offline phase we compute and store a small “sketch ” for each node in the graph, and at query-time we look up the sketches of the source and destination nodes and perform a simple computation using these two sketches to estimate the distance. Categories and Subject Descriptors G.2.2 [Graph Theory]: Graph algorithms, path and circuit problems


Revisiting the Examination Hypothesis with Query Specific Position Bias

Lower Bounds on Near Neighbor Search via Metric Expansion

Prediction strategies without loss

Understanding Fashion Cycles as a Social Choice

A non%2Dexpert view on Turing machines%2C Proof Verifiers%2C and Mental reasoning

Understanding the Cycle of Knowledge Its rise%2C preservation and decay

Deterministic Approximation Algorithms for the Nearest Codeword Problem.

Sparse Cut Projections in Graph Streams.
Abstract. Finding sparse cuts is an important tool for analyzing large graphs that arise in practice, such as the web graph, online social communities, and VLSI circuits. When dealing with such graphs having billions of nodes, it is often hard to visualize global partitions. While studies on sparse cuts have traditionally looked at cuts with respect to all the nodes in the graph, some recent works analyze graph properties projected onto a small subset of vertices that may be of interest in a given context, e.g., relevant documents to a query in a search engine. In this paper, we study how sparse cuts in a graph partition a certain subset of nodes. We call this partition a cut projection. We study the problem of finding cut projections in the streaming model that is appropriate in this context as the input graph is too large to store in main memory. Specifically, for a d-regular graph G on n nodes with a cut of conductance Φ and constant balance, we show how to parti-1 tion a randomly chosen set of k nodes in Õ( αΦ) passes over the graph stream and space Õ(nα + n3/4 k 1/4 αΦ 19/4), for any choice of α ≤ 1. The resulting partition is the projection of a cut of conductance of at most Õ(√Φ). We note that for k &lt; nα 6 Φ O(1) , this can be done in Õ(1/√αΦ) passes and space Õ(nα) that is sublinear in the number of nodes. 1
The Oil Searching Problem.
Abstract. Given n potential oil locations, where each has oil at a certain depth, we seek good trade-offs between the number of oil sources found and the total amount of drilling performed. The cost of exploring a location is proportional to the depth to which it is drilled. The algorithm has no clue about the depths of the oil sources at the different locations or even if there are any. Abstraction of the oil searching problem applies naturally to several life contexts. Consider a researcher who wants to decide which research problems to invest time into. A natural dilemma whether to invest all the time into a few problems, or share time across many problems. When you have spent a lot of time on one problem with no success, should you continue or move to another problem? One could study this problem using a competitive analysis that compares the cost of an algorithm to that of an adversary that knows the depths of the oil sources, but the competitive ratio of the best algorithm for this problem is Ω(n). Instead we measure the performance of a strategy by comparing it to a weaker adversary that knows the set of depths of the oil sources but does not know which location has what depth. Surprisingly, we find that to find k oil sources there is a strategy whose cost is close to that of any adversary that has this limited knowledge of only the set of depths. In particular, we show that if any adversary can find k oil sources with drilling cost B while knowing the set of depths, our strategy finds k − Õ(k5/6) sources with drilling cost B(1+o(1)). This proves that our strategy is very close to the best possible strategy in the total absence of information. 1
3.5%2DWay Cuckoo Hashing for the Price of 2%2Dand%2Da%2DBit.
Abstract. The study of hashing is closely related to the analysis of balls and bins; items are hashed to memory locations much as balls are thrown into bins. In particular, Azar et. al. [2] considered putting each ball in the less-full of two random bins. This lowers the probability that a bin exceeds a certain load from exponentially small to doubly exponential, giving maximum load log log n + O(1) with high probability. Cuckoo hashing [20] draws on this idea. Each item is hashed to two buckets of capacity k. If both are full, then the insertion procedure moves previously-inserted items to their alternate buckets to make space for the new item. In a natural implementation, the buckets are represented by partitioning a fixed array of memory into non-overlapping blocks of size k. An item is hashed to two such blocks and may be stored at any location within either one. We analyze a simple twist in which each item is hashed to two arbitrary size-k memory blocks. (So consecutive blocks are no longer disjoint, but rather overlap by k − 1 locations.) This twist increases the space utilization from 1 − (2/e + o(1)) k to 1 − (1/e + o(1)) 1.59k in general. For k = 2, the new method improves utilization from 89.7 % to 96.5%, yet lookups access only two items at each of two random locations. This result is surprising because the opposite happens in the non-cuckoo setting; if items are not moved during later insertions, then shifting from non-overlapping to overlapping blocks makes the distribution less uniform. 1
Less is more sampling the neighborhood graph makes SALSA better and faster.
In this paper, we attempt to improve the effectiveness and the efficiency of query-dependent link-based ranking algorithms such as HITS, MAX and SALSA. All these ranking algorithms view the results of a query as nodes in the web graph, expand the result set to include neighboring nodes, and compute scores on the induced neighborhood graph. In previous work it was shown that SALSA in particular is substantially more effective than query-independent link-based ranking algorithms such as PageRank. In this work, we show that whittling down the neighborhood graph through consistent sampling of nodes and edges makes SALSA and its cousins both faster (more efficient) and better (more effective). We offer a hypothesis as to why “less is more”, i.e. why using a reduced graph improves performance.
A hardware platform for efficient worm outbreak detection.

Error%2DCorrecting Codes for Ternary Content Addressable Memories.

A Geometric Approach to Lower Bounds for Approximate Near%2DNeighbor Search and Partial Match.
This work investigates a geometric approach to proving cell probe lower bounds for data structure problems. We consider the approximate nearest neighbor search problem on the Boolean hypercube ({0, 1} d,  ‖  · ‖1) with d = Θ(log n). We show that any (randomized) data structure for the problem that answers c-approximate nearest neighbor search queries using t probes must use space at least n1+Ω(1/ct). In particular, our bound implies that any data structure that uses space Õ(n) with polylogarithmic word size, and with constant probability gives a constant approximation to nearest neighbor search queries must be probed Ω(log n / log log n) times. This improves on the lower bound of Ω(log log d / log log log d) probes shown by Chakrabarti and Regev [8] for any polynomial space data structure, and the Ω(log log d) lower bound in Pătras¸cu and Thorup [26] for linear space data structures. Our lower bound holds for the near neighbor problem, where the algorithm knows in advance a good approximation to the distance to the nearest neighbor. Additionally, it is an average case lower bound for the natural distribution for the problem. Our approach also gives the same bound for (2 − 1)-approximation to the farthest neighbor problem. c For the case of non-adaptive algorithms we can improve the bound slightly and show a Ω(log n) lower bound on the time complexity of data structures with O(n) space and logarithmic word size. We also show similar lower bounds for the partial match problem: any randomized t-probe data structure that solves the partial match problem on {0, 1, ⋆} d for d = Θ(log n) must use space n1+Ω(1/t). This implies an Ω(log n / log log n) lower bound for time complexity of near linear space data structures, slightly improving the Ω(log n/(log log n) 2) lower bound from [25],[16] for this range of d. Recently and independently Pătras¸cu achieved similar bounds [24]. Our results also generalize to approximate partial match, improving on the bounds of [4, 25]. 1 1
An Improved Algorithm Finding Nearest Neighbor Using Kd%2Dtrees.
Abstract. We suggest a simple modification to the Kd-tree search algorithm for nearest neighbor search resulting in an improved performance. The Kd-tree data structure seems to work well in finding nearest neighbors in low dimensions but its performance degrades even if the number of dimensions increases to more than two. Since the exact nearest neighbor search problem suffers from the curse of dimensionality we focus on approximate solutions; a c-approximate nearest neighbor is any neighbor within distance at most c times the distance to the nearest neighbor. We show that for a randomly constructed database of points if the query point is chosen close to one of the points in the data base, the traditional Kd-tree search algorithm has a very low probability of finding an approximate nearest neighbor; the probability of success drops exponentially in the number of dimensions d as e −Ω(d/c). However, a simple change to the search algorithm results in a much higher chance of success. Instead of searching for the query point in the Kd-tree we search for a random set of points in the neighborhood of the query point. It turns out that searching for e Ω(d/c) such points can find the c-approximate nearest neighbor with a much higher chance of success. 1
The power of two min%2Dhashes for similarity search among hierarchical data objects.
power of two min-hashes for similarity search among hierarchical
Estimating PageRank on graph streams.
This study focuses on computations on large graphs (e.g., the web-graph) where the edges of the graph are presented as a stream. The objective in the streaming model is to use small amount of memory (preferably sub-linear in the number of nodes n) and a few passes. In the streaming model, we show how to perform several graph computations including estimating the probability distribution after a random walk of length l, mixing time, and the conductance. We estimate the mixing time M of a random walk in Õ(nα+Mα √ q q Mn M n+) space and Õ( α α) passes. Furthermore, the relation between mixing time and conductance gives us an estimate for the conductance of the graph. By applying our algorithm for computing probability distribution on the web-graph, we can estimate the PageRank p of any node up to an additive error of √ ɛp in Õ( q M α) passes and Õ(min(nα + 1
Spamming botnets signatures and characteristics.
In this paper, we focus on characterizing spamming botnets by leveraging both spam payload and spam server traffic properties. Towards this goal, we developed a spam signature generation framework called AutoRE to detect botnet-based spam emails and botnet membership. AutoRE does not require pre-classified training data or white lists. Moreover, it outputs high quality regular expression signatures that can detect botnet spam with a low false positive rate. Using a three-month sample of emails from Hotmail, AutoRE successfully identified 7,721 botnet-based spam campaigns together with 340,050 unique botnet host IP addresses. Our in-depth analysis of the identified botnets revealed several interesting findings regarding the degree of email obfuscation, properties of botnet IP addresses, sending patterns, and their correlation with network scanning traffic. We believe these observations are useful information in the design of botnet detection schemes.
Trace reconstruction with constant deletion probability and related results.

Design Tradeoffs for SSD Performance.
Solid-state disks (SSDs) have the potential to revolutionize the storage system landscape. However, there is little published work about their internal organization or the design choices that SSD manufacturers face in pursuit of optimal performance. This paper presents a taxonomy of such design choices and analyzes the likely performance of various configurations using a trace-driven simulator and workload traces extracted from real systems. We find that SSD performance and lifetime is highly workloadsensitive, and that complex systems problems that normally appear higher in the storage stack, or even in distributed systems, are relevant to device firmware. 1
Better Bounds for Frequency Moments in Random%2DOrder Streams

Deterministic Approximation Algorithms for the Nearest Codeword Problem.

On Finding Frequent Elements in a Data Stream.
We propose an approximate integrated approach for solving both problems of finding the most popular k elements, and finding frequent elements in a data stream coming from a large domain. Our solution is space efficient and reports both frequent and top-k elements with tight guarantees on errors. For general data distributions, our top-k algorithm returns k elements that have roughly the highest frequencies; and it uses limited space for calculating frequent elements. For realistic Zipfian data, the space requirement of the proposed algorithm for solving the exact frequent elements problem decreases dramatically with the parameter of the distribution; and for top-k queries, the analysis ensures that only the top-k elements, in the correct order, are reported. The experiments, using real and synthetic data sets, show space reductions with no loss in accuracy. Having proved the effectiveness of the proposed approach through both analysis and experiments, we extend it to be able to answer continuous queries about frequent and top-k elements. Although the problems of incremental reporting of frequent and top-k elements are useful in many applications, to the best of our knowledge, no solution has been proposed.
Finding Frequent Elements in Non%2Dbursty Streams.
Abstract. We present an algorithm for finding frequent elements in a stream where the arrivals are not bursty. Depending on the amount of burstiness in the stream our algorithm detects elements with frequency at least t with space between Õ(F1/t2)and Õ(F2/t2)whereF1 and F2 are the first and the second frequency moments of the stream respectively. The latter space complexity is achieved when the stream is completely bursty; i.e., most elements arrive in contiguous groups, and the former is attained when the arrival order is random. Our space complexity is Õ(αF1/t 2)whereα is a parameter that captures the burstiness of a stream and lies between 1 and F2/F1. A major advantage of our algorithm is that even if the relative frequencies of the different elements is fixed, the space complexity decreases with the length of the stream if the stream is not bursty. 1
Estimating Sum by Weighted Sampling.

Using Bloom Filters to Speed Up HITS%2DLike Ranking Algorithms.
Abstract. This paper describes a technique for reducing the querytime cost of HITS-like ranking algorithm. The basic idea is to compute for each node in the web graph a summary of its immediate neighborhood (which is a query-independent operation and thus can be done off-line), and to approximate the neighborhood graph of a result set at query-time by combining the summaries of the result set nodes. This approximation of the query-specific neighborhood graph can then be used to perform query-dependent link-based ranking algorithms such as HITS and SALSA. We have evaluated our technique on a large web graph and a substantial set of queries with partially judged results, and found that its effectiveness (retrieval performance) is comparable to the original SALSA algorithm, while its efficiency (query-time speed) is substantially higher. 1
Querying priced information in databases The conjunctive case.

A TCAM%2DBased Parallel Architecture for High%2DSpeed Packet Forwarding.

Computing shortest paths with uncertainty.
We consider the problem of estimating the length of a shortest path in a DAG whose edge  lengths are known only approximately but can be determined exactly at a cost. We obtain both  positive and negative results on both the exact problem and its approximation.  1 
Lower Bounds on Locality Sensitive Hashing.

Fractional Matching Via Balls%2Dand%2DBins.

Exploiting asymmetry in hierarchical topic extraction.

Estimating corpus size via queries.

A dictionary for approximate string search and longest prefix search.

An Improved Construction for Counting Bloom Filters.
Abstract. A counting Bloom filter (CBF) generalizes a Bloom filter data structure so as to allow membership queries on a set that can be changing dynamically via insertions and deletions. As with a Bloom filter, a CBF obtains space savings by allowing false positives. We provide a simple hashing-based alternative based on d-left hashing called a d-left CBF (dlCBF). The dlCBF offers the same functionality as a CBF, but uses less space, generally saving a factor of two or more. We describe the construction of dlCBFs, provide an analysis, and demonstrate their effectiveness experimentally. 1
Achieving anonymity via clustering.
Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of de-identifying records is to remove identifying fields such as social security number, name etc. However, recent research has shown that a large fraction of the US population can be identified using non-key attributes (called quasi-identifiers) such as date of birth, gender, and zip code [15]. Sweeney [16] proposed the k-anonymity model for privacy where non-key attributes that leak information are suppressed or generalized so that, for every record in the modified table, there are at least k−1 other records having exactly the same values for quasi-identifiers. We propose a new method for anonymizing data records, where quasi-identifiers of data records are first clustered and then cluster centers are published. To ensure privacy of the data records, we impose the constraint
Beyond bloom filters from approximate membership checks to approximate state machines.
Many networking applications require fast state lookups in a concurrent state machine, which tracks the state of a large number of flows simultaneously. We consider the question of how to compactly represent such concurrent state machines. To achieve compactness, we consider data structures for Approximate Concurrent State Machines (ACSMs) that can return false positives, false negatives, or a “don’t know” response. We describe three techniques based on Bloom filters and hashing, and evaluate them using both theoretical analysis and simulation. Our analysis leads us to an extremely efficient hashing-based scheme with several parameters that can be chosen to trade off space, computation, and the impact of errors. Our hashing approach also yields a simple alternative structure with the same functionality as a counting Bloom filter that uses much less space. We show how ACSMs can be used for video congestion control. Using an ACSM, a router can implement sophisticated Active Queue Management (AQM) techniques for video traffic (without the need for standards changes to mark packets or change video formats), with a factor of four reduction in memory compared to full-state schemes and with very little error. We also show that ACSMs show promise for real-time detection of P2P traffic.
Entropy based nearest neighbor search in high dimensions.


Balanced allocation on graphs.

Analyzing BitTorrent and related peer%2Dto%2Dpeer networks.


High%2DSpeed and Low%2DPower Network Search Engine Using Adaptive Block%2DSelection Scheme.

Algorithms for the Database Layout Problem.
Abstract. We present a formal analysis of the database layout problem, i.e., the problem of determining how database objects such as tables and indexes are assigned to disk drives. Optimizing this layout has a direct impact on the I/O performance of the entire system. The traditional approach of striping each object across all available disk drives is aimed at optimizing I/O parallelism; however, it is suboptimal when queries co-access two or more database objects, e.g., during a merge join of two tables, due to the increase in random disk seeks. We adopt an existing model, which takes into account both the benefit of I/O parallelism and the overhead due to random disk accesses, in the context of a query workload which includes co-access of database objects. The resulting optimization problem is intractable in general and we employ techniques from approximation algorithms to present provable performance guarantees. We show that while optimally exploiting I/O parallelism alone suggests uniformly striping data objects (even for heterogeneous files and disks), optimizing random disk access alone would assign each data object to a single disk drive. This confirms the intuition that the two effects are in tension with each other. We provide approximation algorithms in an attempt to optimize the trade-off between the two effects. We show that our algorithm achieves the best possible approximation ratio. 1
Anonymizing Tables.
Privacy is a serious concern when microdata need to be released for ad hoc analyses. The privacy goals of existing privacy protection approaches (e.g., �-anonymity and �-diversity) are suitable only for categorical sensitive attributes. Since applying them directly to numerical sensitive attributes (e.g., salary) may result in undesirable information leakage, we propose privacy goals to better capture the need of privacy protection for numerical sensitive attributes. Complementing the desire for privacy is the need to support ad hoc aggregate analyses over microdata. Existing generalization-based anonymization approaches cannot answer aggregate queries with reasonable accuracy. We present a general framework of permutationbased anonymization to support accurate answering of aggregate queries and show that, for the same grouping, permutation-based techniques can always answer aggregate queries more accurately than generalization-based approaches. We further propose several criteria to optimize permutations for accurate answering of aggregate queries, and develop efficient algorithms for each criterion. 1
Efficient hashing with lookups in two memory accesses.

Entropy based Nearest Neighbor Search in High Dimensions

Balanced Allocation on Graphs

Lower bounds on Locality Sensitive Hashing

The smallest grammar problem.
This thesis considers the smallest grammar problem: find the smallest context-free grammar that generates exactly one given string. We show that this problem is intractable, and so our objective is to find approximation algorithms. This simple question is connected to many areas of research. Most importantly, there is a link to data compression; instead of storing a long string, one can store a small grammar that generates it. A small grammar for a string also naturally brings out underlying patterns, a fact that is useful, for example, in DNA analysis. Moreover, the size of the smallest context-free grammar generating a string can be regarded as a computable relaxation of Kolmogorov complexity. Finally, work on the smallest grammar problem qualitatively extends the study of approximation algorithms to hierarchically-structured objects. In this thesis, we establish hardness results, evaluate several previously proposed algorithms, and then present new procedures with much stronger approximation guarantees.
Minimum Enclosing Polytope in High Dimensions

Efficient Hashing with Lookups in two Memory Accesses

Clustering to minimize the sum of cluster diameters.
  We study the problem of clustering points in a metric space so as to minimize the sumof cluster diameters or the sum of cluster radii. Significantly improving on previous results, we present
Combining request scheduling with web caching.
CWI is a founding member of ERCIM, the European Research Consortium for Informatics and Mathematics. CWI&#039;s research has a theme-oriented structure and is grouped into four clusters. Listed below are the names of the clusters and in parentheses their acronyms.
Representing Graph Metrics with Fewest Edges.
Abstract We consider the problem of obtaining compressed representations for graph metrics by adding extra (&amp;quot;Steiner&amp;quot;) vertices and removing edges, while preserving distances. The compression factor achieved is the ratio k between the number of edges in the original graph and the number in the compressed graph. We consider metrics that, even without the addition of Steiner vertices, can be represented by graphs with uniform edge-weights. We show that for metrics of this type, the only beneficial compressions possible with the addition of Steiner vertices consist of replacing cliques by stars, in which the center vertex is a Steiner vertex. We give a 2-approximation algorithm to the problem of compressing the best single clique, and show the problem is as hard to approximate as vertex cover. We give a 3 log k-approximation algorithm with respect to an optimum that selects disjoint cliques, and a c p k log k-approximation algorithm with respect to an optimum where each clique compressed intersects a constant number of the other cliques compressed. These algorithms extend to the bipartite case, where complete bipartite subgraphs are compressed. Finally, we show that compression by cliques is hard to approximate within n 1=2\Gamma ffl on instances with optimum compression at most n
Computing Shortest Paths with Uncertainty.
We consider the problem of estimating the length of a shortest path in a DAG whose edge  lengths are known only approximately but can be determined exactly at a cost. We obtain both  positive and negative results on both the exact problem and its approximation.  1 
Better streaming algorithms for clustering problems.
We study cluster ng pr blems in the str aming model,  wher  e the goal is to  cluster  a set of points by making one pass  (or  a few passes)  over  the data using a small amount of storSD  space.Our mainr  esult is a r ndomized  algor  ithm  for  k--Median prE lem which p duces a constant  factor appr  oximation in one pass using storR4 space O(kpolylog n). This is a significant imp r vement of the prS ious best algor5 hm which yielded a 2    appr ximation using O(n    )space.
Sorting and Searching using Ternary CAMs.

A combinatorial algorithm for MAX CSP.

Computing the Median with Uncertainty.

Sorting and Searching Using Ternary CAMs.

Reducing TCAM Power Consumption and Increasing Throughput.

New Algorithms for Subset Query
- N * 2O(m log 2 mpc / log N) space, and O(N/2c) time, for any c- Nmc space and O(mN/c) query time, for any c &lt; = N We extend these results to the more general problem of orthogonal range searching (both exact and approximate versions), approximate orthogonal range intersection and the exact and approximate versions of the nearest neighbor problem in `1. 1 Introduction The subset query problem is defined as follows: given a set P of N subsets ofa universe U, |U |  = m, build a data structure, which for any query set Q ae Udetects if there is any
Web caching with request reordering.
Current web caching algorithms process requests in the order of the arrival. While such restriction is inevitable in system paging due to the sequential nature of a program, the HTTP requests are (essentially) independent at a high volume proxy server. This gives a proxy server the exibility to reorder requests, provided no request is inordinately delayed. The expectation is that reordering requests may lead to better performance. We formulate an online k- reordering problem that captures such phenomenon for unit caches. We give a dynamic programming algorithm to solve the oine case. We give O(1) upper and lower bound on the competitive ratio of the online algorithms. We also generalize this problem to any metric space.
Approximating the smallest grammar Kolmogorov complexity in natural models.
We consider the problem of finding the smallest context-free grammar that generates exactly one given string of length n. The size of this grammar is of theoretical interest as an efficiently computable variant of Kolmogorov complexity. The problem is of practical importance in areas such as data compression and pattern extraction. The smallest grammar...
Clustering to minimize the sum of cluster diameters.
  We study the problem of clustering points in a metric space so as to minimize the sumof cluster diameters or the sum of cluster radii. Significantly improving on previous results, we present
On the decidability of accessibility problems %28extended abstract%29.
Protection systems have provided the formal basis for the study of security and access mechanisms in computer systems for many years and, more recently, in the context of trust management. The main objective in the design and analysis of such systems is to express policies that prescribe how objects interact and share information with each other, and verify that undesirable actions cannot take place. The latter problem is referred to as the safety or accessibility problem, since it is often phrased in the form &#034;Can object p gain (illegal) access to object q by a series of legal moves (as prescribed by a policy)?&#034;. Much work has gone into designing protection systems that have signi cant expressive power and e ective procedures for verifying accessibility. In this paper, we study one such general protection system, providing algorithms for deciding accessibility within the system. Our methods involve relating this problem to membership problems for certain classes of grammars, and reveal interesting connections between protection systems and the grammars that describe them. Of independent interest is the discovery of an elegantly characterised family of grammars that to the best of our knowledge has not been placed within
Computing the median with uncertainty.

An O%28log%2A n%29 Approximation Algorithm for the Asymmetric p%2DCenter Problem.

Consistent Hashing and Random Trees Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web.
We describe a family of caching protocols for distrib-uted networks that can be used to decrease or eliminate the occurrence of hot spots in the network. Our protocols are particularly designed for use with very large networks such as the Internet, where delays caused by hot spots can be severe, and where it is not feasible for every server to have complete information about the current state of the entire network. The protocols are easy to implement using existing network protocols such as TCP/IP, and require very little overhead. The protocols work with local control, make efficient use of existing resources, and scale gracefully as the network grows. Our caching protocols are based on a special kind of hashing that we call consistent hashing. Roughly speaking, a consistent hash function is one which changes minimally as the range of the function changes. Through the development of good consistent hash functions, we are able to develop caching protocols which do not require users to have a current or even consistent view of the network. We believe that consistent hash functions may eventually prove to be useful in other applications such as distributed name servers and/or quorum systems. 1
A Note on Optical Routing on Trees.
Bandwidth is a very valuable resource in wavelength division multiplexed optical networks. The problem of finding an optimal assignment of wavelengths to requests is of fundamental importance in bandwidth utilization. We present a polynomialtime algorithm for this problem on fixed constant-size topologies. We combine this algorithm with ideas from Raghavan and Upfal [15] to obtain an optimal assignment of wavelengths on constant degree undirected trees. Mihail, Kaklamanis, and Rao [14] posed the following open question: what is the complexity of this problem on directed trees? We show that it is NP-complete both on binary and constant depth directed trees.  Keywords: Algorithms, Combinatorial Problems, Computational Complexity, Interconnection Networks. 1 Introduction Motivation. Developments in fiber-optic networking technology using Wavelength Division Multiplexing (WDM) have finally reached the point where it  1  Supported by ONR Young Investigator Award N00014-93-1-0590. This work ...
